from Pila import *
from Cola import *
from Utilidades import *
from Pieza import *
from Nodo import *
import random


#al ppio debe estar el nodo inicial anadido
def busqueda_profundidad(imagen, estado_inicial):
    
    profundidad = 0
    solucion = []
    frontera = Cola(estado_inicial)
    
    while True :
        nodoActual = frontera.contenedor.pop()
        
        if TestObjetivo(nodoActual,imagen,profundidad):
                
            camino = []

        
            #Reconstruimos la solucion
            while nodoActual.padre != None :
                camino.append(nodoActual.accion)
                nodoActual = nodoActual.padre
            
            camino.reverse()
            solucion = camino
            
            return solucion
                    
            
        else : 
            es = expandir(nodoActual, imagen)
            #Realizo insercion aleatoria
            for i in range(len(es)) :
                bran = random.choice(es)
                frontera.insertar(bran)
                es.remove(bran)
        
                                        
        
    
def busqueda_anchura(imagen, estado_inicial) :
    #Comienza la busqueda
    profundidad = 0
    frontera = Cola(estado_inicial)

    while True :
        #Si la frontera esta vacia se termina la busqueda sin soluciones
        if (frontera.esVacia()) :
            solucion = []
            return solucion


        #si aun quedan nodos en la frontera seguimos explorando el espacio de estados
        else:
            nodo = frontera.getelemento()
            if nodo != [] :
                #Comprobamos si hemos llegado a una solucion
                if TestObjetivo(nodo,imagen,profundidad) :
                    print "Se ha encontrado Solucion"
                    camino = []
                    #Construimos la solucion recorriendo las acciones desde la hoja hasta la raiz
                    while nodo.padre != None :
                        camino.append(nodo.accion)
                        nodo = nodo.padre

                    camino.reverse()
                    solucion = camino
                    return camino

                else :

                    es = expandir(nodo,imagen)
                    profundidad += 1

                    #Insertamos los nodos en la frontera de manera aleatoria
                    for i in range(len(es)) :
                        bran = random.choice(es)
                        frontera.insertar(bran)
                        es.remove(bran)


#Realiza la una busqueda en profundidad hasta un determinado nivel "limite" de profundiad en el arbol
def busqueda_profundidad_limitada(imagen, estado_inicial, limite):
    profundidad = 0
    solucion = []
    frontera = Cola(estado_inicial)
    
    while True :
        nodoActual = frontera.contenedor.pop()
        
        if TestObjetivo(nodoActual,imagen,profundidad):
                
            camino = []
            #Reconstruimos la solucion
            while nodoActual.padre != None :
                camino.append(nodoActual.accion)
                nodoActual = nodoActual.padre
                    
                camino.reverse()
                solucion = camino
                return solucion
            
        else : 
            if profundidad == limite :
                solucion = []
                return solucion
            else:
                es = expandir(nodoActual, imagen)
                for i in range(len(es)) :
                    bran = random.choice(es)
                    frontera.insertar(bran)
                    es.remove(bran)
                    

def profundidad_iterativa(imagen, estado_inicial):
    prof_limite = 0
    solucion = []
    
    while True :
        solucion = busqueda_profundidad_limitada(imagen, estado_inicial, prof_limite)
        if solucion != [] :
            return solucion
        else : #Si no se ha econtrado una solucion aumentamos el limite en una unidad
                # e intentamos encontrarla con el nuevo limite, lo cual se hara en la
                #siguiente pasada del bucle
            prof_limite = prof_limite +1



#******************* COSTO UNIFORME *********************
def costo_uniforme(imagen, estado_inicial) :
    #Comienza la busqueda
    profundidad = 0
    frontera = Cola(estado_inicial)


    while True :
        #Si la frontera esta vacia se termina la busqueda sin soluciones
        if (frontera.esVacia()) :
            solucion = []
            return solucion


        #si aun quedan nodos en la frontera seguimos explorando el espacio de estados
        else:
            nodo = frontera.getelemento()
            if nodo != [] :
                #Comprobamos si hemos llegado a una solucion
                if TestObjetivo(nodo,imagen,profundidad) :
                    print "Se ha encontrado Solucion"
                    camino = []
                    #Construimos la solucion recorriendo las acciones desde la hoja hasta la raiz
                    while nodo.padre != None :
                        camino.append(nodo.accion)
                        nodo = nodo.padre

                    camino.reverse()
                    solucion = camino
                    return camino

                else :
                    
                    es = expandir(nodo,imagen)
                    profundidad += 1

                    #Insertamos los nodos en la frontera
                    frontera.anadir(es)
                    #Ordenamos la frontera, para tomar primero el nodo de menor coste
                    #se ordenan por tanto de menor a mayor en funcion del coste del nodo
                    frontera.contenedor = sorted(frontera.contenedor, key=lambda nodo: nodo.costo)
                    
    
    


#*********** HASTA AQUI LOS ALGORITMOS DE BUSQUEDA ******************

###################################################################################
# Expande un nodo dado, devolviendo los nodos hijos en el domino del problema dado.
#Se tratara la insercion de los mismos en la frontera de forma externa a este metodo.
###################################################################################
def expandir(nodo, imagen) :
    
    sucesores = []
    modificados = []
    pix_modify = nodo.pixeles_modificados
    coste = 0
    color_pieza = 0


    for i in range(0,len(imagen)) :
        for j in range(0,len(imagen[0])) :
            for k in range(1,133) :
                costo = 4
                color_ficha = k%7
                modificados = []
                modificados = colocar(nodo.pixeles_modificados, i, j, len(imagen), len(imagen[0]), k)
                
                if modificados != [] :
                    
                    
                    for pixel in modificados :
                        if (imagen[pixel[0]][pixel[1]].color) == color_ficha :
                            costo = costo -1
                        
                    #los pixeles modificados hasta el momento seran los recien modificados y los 
                    #modificados por el padre, abuelo, ...                  
                    sucesor = Nodo(nodo, (nodo.pixeles_modificados+modificados), [i,j,k],costo,nodo.profundidad+1)
                    sucesores.append(sucesor)
                    modificados = []
                    pix_modify = []

    return sucesores


####################################################################
#Metodo que devuelve la posicion dentro de la imagen de los pixeles
#que modificaria la accion de poner la pieza tipo en la poscion x,y
#si es posible realizar dicha accion, en caso contrario devolvera
#una matriz vacia 
#Aclaracion :imagen se refiere a los  pixeles modificados
####################################################################
def colocar(imagen, x, y, tam_x, tam_y, tipo) :
    
    pix_modify  = []
    color = tipo%7

    
    if tipo>0 and tipo <8 :
        
        if not([x,y]in imagen) and not([x+1,y]in imagen) and not([x+2,y]in imagen) and not([x+3,y]in imagen) and (x+3)<tam_x :
            pix_modify = [[x,y],[x+1,y],[x+2,y],[x+3,y]]


    elif tipo>7 and tipo<15 : 
        if not([x,y] in imagen) and not([x,y+1] in imagen) and not([x,y+2]in imagen) and not([x,y+3]in imagen) and (y+3)<tam_y :
            pix_modify = [[x,y],[x,y+1],[x,y+2],[x,y+3]]
        
    elif tipo>14 and tipo<22 :
        
        if not([x,y]in imagen) and not([x,y-1]in imagen) and not([x+1,y-1]in imagen) and not([x+2,y-1]in imagen) and (x+2)<tam_x and (y-1)>=0 :
            pix_modify = [[x,y],[x,y-1],[x+1,y-1],[x+2,y-1]]
            
    elif tipo>21 and tipo<29 :
        

        if not([x,y] in imagen) and not([x+1,y] in imagen) and not([x+1,y+1]in imagen) and not([x+1,y+2] in imagen) and (x+1)< tam_x and (y+2) < tam_y :
            pix_modify = [[x,y],[x+1,y],[x+1,y+1],[x+1,y+2]]
            
        
    elif tipo>28 and tipo<36 :
        
        if not([x,y]in imagen) and not([x,y+1]in imagen) and not([x-1,y+1]in imagen) and not([x-2,y+1]in imagen) and (x-2)>= 0 and (y+1)<tam_y:
            pix_modify = [[x,y],[x,y+1],[x-1,y+1],[x-2,y+1]]

    elif tipo>35 and tipo<43 :
        
        if not([x,y]in imagen) and not([x-1,y]in imagen) and not([x-1,y-1] in imagen) and not([x-1,y-2]in imagen) and (x-1)>= 0 and (y-2)>= 0 :
            pix_modify = [[x,y],[x-1,y],[x-1,y-1],[x-1,y-2]]

    elif tipo>42 and tipo<50 :
        
        if not([x+2,y]in imagen) and not([x,y-1]in imagen) and not([x+1,y-1]in imagen) and not([x+2,y-1]in imagen) and (x+2)<tam_x and (y-1)>=0 :
            
            pix_modify = [[x+2,y],[x,y-1],[x+1,y-1],[x+2,y-1]]

    elif tipo>49 and tipo<57 :
        
        if not([x+1,y]in imagen) and not([x+1,y+1]in imagen) and not([x+1,y+2]in imagen) and not([x,y+2]in imagen) and (x+1)<tam_x and (y+2)<tam_y :
            
            pix_modify = [[x+1,y],[x+1,y+1],[x+1,y+2],[x,y+2]]

    elif tipo>56 and tipo<64 :
        
        if not([x-2,y]in imagen) and not([x-2,y+1]in imagen) and not([x-1,y+1]in imagen) and not([x,y+1]in imagen) and (x-2)>=0 and (y+1)<tam_y :
            
            pix_modify = [[x-2,y],[x-2,y+1],[x-1,y+1],[x,y+1]]

    elif tipo>63 and tipo<71 :
        
        if not([x-1,y] in imagen) and not([x-1,y-1]in imagen) and not([x-1,y-2]in imagen) and not([x,y-2]in imagen) and (x-1)>=0 and (y-2)>=0 :
            
            pix_modify = [[x-1,y],[x-1,y-1],[x-1,y-2],[x,y-2]]

    elif tipo>70 and tipo<78 :

        if not([x,y]in imagen) and not([x+1,y]in imagen) and not([x,y-1]in imagen) and not([x+1,y-1]in imagen) and (y-1)>=0 and (x+1)<tam_x :

            pix_modify = [[x,y],[x+1,y],[x,y-1],[x+1,y-1]]

    elif tipo>77 and tipo<85 :
        
        if not([x+1,y] in imagen) and not([x+2,y]in imagen) and not([x,y-1]in imagen) and not([x+1,y-1]in imagen) and (x+2)<tam_x and (y-1)>=0 :
            
            pix_modify = [[x+1,y],[x+2,y],[x,y-1],[x+1,y-1]]

    
    elif tipo>84 and tipo<92 :
        
        if not([x+1,y]in imagen) and not([x+1,y+1]in imagen) and not([x,y+1]in imagen)and not([x,y+2]in imagen) and (x+1)<tam_x and (y+2)<tam_y :
            
            pix_modify = [[x+1,y],[x+1,y+1],[x,y+1],[x,y+2]]

    elif tipo>91 and tipo<99 :
        
        if not([x,y]in imagen) and not([x+1,y]in imagen) and not([x+1,y-1]in imagen)and not([x+2,y-2]in imagen) and (x+2)<tam_x and (y-2)>=0 :
            
            pix_modify = [[x,y],[x+1,y],[x+1,y-1],[x+2,y-2]]

    elif tipo>98 and tipo<106 :
        
        if not([x,y]in imagen) and not([x,y-1]in imagen) and not([x-1,y-1]in imagen)and not([x-1,y-2]in imagen) and (x-1)>=0 and (y-2)>=0 :
            
            pix_modify = [[x,y],[x,y-1],[x-1,y-1],[x-1,y-2]]

    elif tipo>105 and tipo<113 :
        
        if not([x,y-1]in imagen) and not([x+1,y]in imagen)and not([x+1,y-1]in imagen) and not([x+2,y-1]in imagen) and (x+2)<tam_x and (y-1)>=0 :
            
            pix_modify = [[x,y-1],[x+1,y],[x+1,y-1],[x+2,y-1]]
            
    elif tipo>112 and tipo<120 :
        
        if not([x,y+1]in imagen) and not([x+1,y] in imagen) and not([x+1,y+1]in imagen) and not([x+1,y+2]in imagen) and (x+1)<tam_x and (y+2)<tam_y :
            
            pix_modify = [[x,y+1],[x+1,y],[x+1,y+1],[x+1,y+2]]

    elif tipo>119 and tipo<127 :

        if not([x,y+1]in imagen) and not([x-1,y]in imagen) and not([x-1,y+1]in imagen) and not([x-2,y+1]in imagen) and (x-2)>= 0 and (y+1)<tam_y :
            pix_modify = [[x,y+1],[x-1,y],[x-1,y+1],[x-2,y+1]]
            
    else :
        if not([x-1,y] in imagen) and not([x-1,y-1] in imagen)and not([x-1,y-2] in imagen) and not([x,y-1] in imagen) and x-1>=0 and y-2>=0:
            pix_modify = [[x-1,y],[x-1,y-1],[x-1,y-2],[x,y-1]]
            



        
    return pix_modify

#################################################################
#Dada un determinado nodo indica si se trata de un nodo solucion
#o no, mediante la devolución de un valor booleano         
#################################################################
def TestObjetivo(nodo,imagen,profundidad) :

    objetivo = True
    i = 0
    j = 0
    k = 0
    k = 1
    modificados = []
    mod_total = []

    i = 0
    while i< len(imagen) and objetivo == True:
        j = 0
        while j < len(imagen[0]) and objetivo == True :
            k = 0
            while k <= 133 and objetivo == True:
                modificados = colocar(nodo.pixeles_modificados,i,j,len(imagen),len(imagen[0]),k)
                if modificados != [] :
                    objetivo = False
                k = k+1
            j = j+1
        i = i+1


    return objetivo
            
